package net.lainiao.leetcode;

public class lintcode41 {
    //最大子数组
    public static void main(String[] args) {
        int[] nums={-2,2,-3,4,-1,2,1,-5,3};
        int res=GetMaxSubArray(nums);
        System.out.println(res);
    }

    public static int GetMaxSubArray(int[] nums){
        int ans=nums[0];
        int sum=ans;
        for (int i = 1; i <nums.length ; i++) {
            if(sum<0){
                sum=nums[i];
            }else{
                sum+=nums[i];
            }
            if(sum>ans){
                ans=sum;
            }
        }
        return ans;
    }
}
